package com.njupt.DynamicProgramming;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/17 11:06
 * @Description: 139. 单词拆分
 * @Version: 1.0
 */


public class WordBreak_139 {

    /**
     * 贪心法，会错误
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak1(String s, List<String> wordDict) {
        StringBuilder sb = new StringBuilder(s);

        for (int i = 0; i < wordDict.size(); i++) {
            String s1 = wordDict.get(i);
            while(s.contains(s1)){
                int index = s.indexOf(s1);
                sb.delete(index,index + s1.length());
                s = sb.toString();
            }
        }

        return sb.toString().equals("") ? true : false;
    }

    /**
     * 动态规划法
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() +1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (String word : wordDict){
                int len = word.length();
                if(i>= len && dp[i-len] && word.equals(s.substring(i-len,i))){
                    dp[i] = true;
                    break;
                }

            }

        }
        return dp[s.length()];
    }

    public static void main(String[] args) {
        String[] wordDict = {"leet","code"};
        List list = new ArrayList<>(Arrays.asList("leet","code"));
        String s = "leetcode";
        WordBreak_139 test = new WordBreak_139();
        System.out.println(test.wordBreak(s, list));

    }
}
